package run.siyuan.jdk.漫画算法.链表;

/**
 * @ClassName LinkedInsertDemo
 * @Description TODO
 * @Author siyuan
 * @Date 2023/4/7 22:39
 */
public class LinkedInsertDemo {

    /**
     * 头节点
     */
    private Node head = new Node();

    /**
     * 尾节点
     */
    private Node last;
    /**
     * 已插入的元素
     */
    private int size;

    public static void main(String[] args) {
        LinkedInsertDemo linked = new LinkedInsertDemo();
        // 尾部插入
//        linked.wbInsert(1);
//        linked.wbInsert(2);

        // 头部插入
//        linked.tbInsert(1);
//        linked.tbInsert(2);

        // 中间插入
        linked.zjInsert(0, 0);
        linked.zjInsert(1, 1);
        linked.zjInsert(2, 2);
        linked.zjInsert(3, 3);
        linked.zjInsert(4, 4);
        linked.zjInsert(3, 3333);

        linked.show();
        // 头部删除
//        linked.tbDelete();
//        linked.tbDelete();
//        linked.tbDelete();
//        linked.tbDelete();
//        linked.tbDelete();

        // 尾部删除
//        linked.wbDelete();
//        linked.wbDelete();
//        linked.wbDelete();
//        linked.wbDelete();
//        linked.wbDelete();

        // 中间删除
        linked.zjDelete(1);
        linked.zjDelete(1);
        linked.zjDelete(1);
        linked.zjDelete(1);


        linked.show();
    }

    /**
     * 头部插图
     *
     * @param element
     */
    public void tbInsert(int element) {

        Node node = new Node(element);
        node.next = head.next;
        head.next = node;
        if (size == 0) {
            last = node;
        }
        size++;
    }

    /**
     * 中间插入插图
     *
     * @param element
     */
    public void zjInsert(int index, int element) {
        if (index < 0 || index > size) {
            throw new RuntimeException("下标越界");
        }
        Node v = new Node(element);
        if (size == 0) {
            last = v;
            head.next = last;
        } else if (size > 0) {
            Node node = head.next;
            int i = 0;
            while (node != null) {
                // 上一个next 指向新节点
                if (i == index - 1) {
                    Node n = v;
                    n.next = node.next;
                    node.next = n;
                }
                node = node.next;
                i++;
            }
        }
        size++;
    }

    /**
     * 尾部插入
     *
     * @param element 插入的元素
     */
    public void wbInsert(int element) {
        if (size == 0) {
            last = new Node(element);
            this.head.next = last;

        } else if (size > 0) {
            Node node = new Node(element);
            last.next = node;
        }
        size++;
    }

    /**
     * 打印
     */
    public void show() {
        Node node = head.next;
        int index = 0;
        while (node != null) {
            System.out.printf("%d\t%d\n", index, node.data);
            index++;
            node = node.next;
        }
    }

    /**
     * 头部删除
     */
    public void tbDelete() {
        if (size == 0) {
            throw new RuntimeException("空链表，删除失败");
        }
        head.next = head.next.next;
        size--;
    }

    /**
     * 中间删除
     *
     * @param index
     */
    public void zjDelete(int index) {
        if (size == 0) {
            throw new RuntimeException("空链表，删除失败");
        }
        Node upperNode = getNode(index - 1);
        Node currntNode = upperNode.next;
        upperNode.next = currntNode.next;
        size--;
    }

    /**
     * 尾部删除
     */
    public void wbDelete() {
        if (size == 0) {
            throw new RuntimeException("空链表，删除失败");
        }
        Node node = getNode(size - 2);
        last = node;
        node.next = null;
        size--;
    }

    /**
     * 获取指定下标的元素
     *
     * @param index
     * @return
     */
    private Node getNode(int index) {
        Node node = head.next;
        for (int j = 0; j < index; j++) {
            node = node.next;
        }
        return node;
    }


    /**
     * 单向链表
     */
    class Node {
        private int data;
        private Node next;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }
    }

}
